package com.yun.algorithmproblem.leetcode;

import java.util.*;

/**
 * 855. 考场就座
 * <p>
 * 在考场里，一排有 N 个座位，分别编号为 0, 1, 2, ..., N-1 。
 * <p>
 * 当学生进入考场后，他必须坐在能够使他与离他最近的人之间的距离达到最大化的座位上。如果有多个这样的座位，他会坐在编号最小的座位上。(另外，如果考场里没有人，那么学生就坐在 0 号座位上。)
 * <p>
 * 返回 ExamRoom(int N) 类，它有两个公开的函数：其中，函数 ExamRoom.seat() 会返回一个 int （整型数据），代表学生坐的位置；函数 ExamRoom.leave(int p) 代表坐在座位 p 上的学生现在离开了考场。每次调用 ExamRoom.leave(p) 时都保证有学生坐在座位 p 上。
 */
public class Leetcode855 {

    public static void main(String[] args) {
        int[] operate = new int[]{-1, -1, -1, 0, 4};
        ExamRoom e = new ExamRoom(10);
        for (int i : operate) {
            if (i == -1) {
                int seat = e.seat();
                System.out.println(seat);
            } else {
                e.leave(i);
            }
        }
    }

    static class ExamRoom {

        int n;
        TreeSet<Integer> seats;
        PriorityQueue<int[]> pq;

        public ExamRoom(int n) {
            this.n = n;
            this.seats = new TreeSet<>();
            this.pq = new PriorityQueue<>(new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    int d1 = o1[1] - o1[0], d2 = o2[1] - o2[0];
                    return d1 / 2 == d2 / 2 ? o1[0] - o2[0] : d2 - d1;
                }
            });
        }

        public int seat() {
            if (seats.isEmpty()) {
                seats.add(0);
                return 0;
            }
            int left = seats.first();
            int right = n - 1 - seats.last();
            while (seats.size() >= 2) {
                int[] peek = pq.peek();
                if (seats.contains(peek[0]) && seats.contains(peek[1]) && seats.higher(peek[0]) == peek[1]) {//不属于延迟删除的区间
                    int d = peek[1] - peek[0];
                    if (d / 2 <= left || d / 2 < right) {//左边或者右边最佳
                        break;
                    }
                    pq.poll();
                    pq.offer(new int[]{peek[0], peek[0] + d / 2});
                    pq.offer(new int[]{peek[0] + d / 2, peek[1]});
                    seats.add(peek[0] + d / 2);
                    return peek[0] + d / 2;
                }
                pq.poll();//leave函数中延迟删除的区间在此时删除
            }
            if (right > left) { // 最右的位置更优
                pq.offer(new int[]{seats.last(), n - 1});
                seats.add(n - 1);
                return n - 1;
            } else {
                pq.offer(new int[]{0, seats.first()});
                seats.add(0);
                return 0;
            }
        }

        public void leave(int p) {
            if (p != seats.first() && p != seats.last()) {
                int pre = seats.lower(p), next = seats.higher(p);
                pq.offer(new int[]{pre, next});
            }
            seats.remove(p);
        }
    }
}
